

public class Sort {
    /**
     * 1.直接插入排序算法
     * 时间复杂度：1+2+...n = O(n*n)
     *     最好的情况是O(n)：即当数据趋于有序的时候，时间复杂度越低，
     *                     所以当数据基本有序的时候，建议使用直接插入排序
     * 空间复杂度：O(1)
     * 稳定性：稳定
     *        如果一个排序是稳定的，可以改为不稳定的
     *        如果一个排序是不稳定的，改不成稳定的
     * @param array
     */
    public static void insertSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int j = i - 1;
            for (; j >= 0 ; j--) {
                //此时这个地方取等号就是不稳定的
                if(array[j] > tmp) {
                    array[j+1] = array[j];
                } else {
                    //array[j + 1 ] = tmp;
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }

    //第二次练习  直接插入排序法
    public static void insertSort2(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];   //把值给先存起来
            int j = i - 1;
            for (; j >= 0; j--) {
                if(array[j] > tmp) {
                    array[j + 1] = array[j];
                } else {
                    array[j + 1] = tmp;  //这个可以不写，因为跳出循环后也要执行
                    break;
                }
            }
            //走到这说明j不满足循环条件了，即是j = -1  或者是提前跳出循环表示前面的已经有序，此时把tmp的值给到j = 0
            array[j + 1] = tmp;
        }
    }
    //第三次练习  直接插入排序法
    //时间复杂度：n^2  空间 1  稳定
    public static void insertSort3(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int j = i - 1;
            for (; j >= 0 ; j--) {
                if(array[j] > tmp) {
                    array[j + 1] = array[j];
                } else {
                    array[j + 1] = tmp;
                    break;
                }
            }
            array[j + 1] = tmp;
        }
    }

    /**
     * 2.希尔排序  : 直接插入排序算法的一种改进
     * 时间复杂度：O(N^1.3)
     * 空间复杂度：O(1)
     * 稳定性：不稳定的排序
     * @param array
     */
    public static void shellSort(int[]  array){
        int gap = array.length;
        while(gap > 1) {
            shell(array,gap);
            gap /= 2;
        }
        //整体进行一次希尔排序
        shell(array,1);
    }

    public static void shell(int[]  array,int gap) {
        for (int i = gap; i < array.length; i++) {
            int tmp = array[i];
            int j = i - gap;
            for (; j >= 0 ; j -= gap) {
                if(array[j] > tmp) {
                    array[j+gap] = array[j];
                } else {
                    //array[j + 1 ] = tmp;
                    break;
                }
            }
            array[j+gap] = tmp;
        }
    }


    //第二次练习希尔排序
    public static void shellSort2(int[]  array) {
        int gap = array.length;
        while(gap > 1) {
            gap /= 2;
            shell2(array,gap);
        }
    }
    public static void shell2(int[]  array,int gap) {
        for (int i = gap; i < array.length; i++) {
            int tmp = array[i];
            int j = i - gap;
            for (; j >= 0 ; j -= gap) {
                if(array[j] > tmp) {
                    array[j + gap] = array[j];
                } else {
                    array[j + gap ] = tmp;
                    break;
                }
            }
            array[j + gap ] = tmp;
        }
    }
    /**
     * 3.选择排序算法
     * 时间复杂度：O(N^2)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
      * @param array
     */
    public static void selectSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            int j = i + 1;
            //找到最小值的下标
            for (; j < array.length; j++) {
                if(array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            //进行交换
            swap(array,i,minIndex);
        }
    }
    //交换函数 进行封装起来
    private static void swap(int[] array,int i,int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    //第二次练习直接排序法
    public static void selectSort2(int[] array) {
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                if(array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            //走出这个循环，表示minIndex存的就是最小值的下标
            //进行最小值和array[i] 交换  即是：array[i] 和 array[minIndex]
            swap(array,i,minIndex);
        }
    }

    //第三次练习直接排序法 ,把后面的最小值跟最前面的值进行交换
    //时间复杂度：O（N^2）  空间复杂度O（1）  不稳定
    public static void selectSort3(int[] array) {
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                if(array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            swap(array,minIndex,i);
        }
    }
    /**
     * 4.冒泡排序法
     * @param array
     */
    public static void bubbleSort(int[] array) {
        //最外层表示趟数
        for (int i = 0; i < array.length; i++) {
            //此层表示比较的次数
            boolean flag = true;
            for (int j = 0; j < array.length - 1 - i; j++) {  //注意这个地方一定要减1，
                                                             // 因为最后是倒数两个数比较 如果不减1 array【j】 是最后一个数，那么j+1 就会数组越界
                if(array[j + 1] > array[j]) {   //默认是大的数往前跑，相当于泡大的往上面飘，该成小于号，最后结果就是从很小到大
                    //进行交换
                    swap(array,j,j + 1);
                    flag = false;
                }
            }
            if(true == flag) {  //说明没有进行交换的数，则就是已经排好序了
                break;
            }
        }
    }

    /**
     * 5.堆排序：
     * 时间复杂度：O(N*logn)
     * 空间复杂度：O(1)
     * 稳定性：不稳定的排序
     * @param array
     */
    public static void heapSort(int[] array) {
        createBigHeap(array);
        int end = array.length-1;
        while (end > 0) {
            swap(array,0,end);
            shiftDown(array,0,end);
            end--;
        }
    }

    private static void createBigHeap(int[] array) {
        for (int parent = (array.length-1-1)/2; parent >= 0 ; parent--) {
            shiftDown(array,parent,array.length);
        }
    }

    private static void shiftDown(int[] array,int parent,int len) {
        int child = 2*parent+1;
        while (child < len) {
            if(child+1 < len && array[child] < array[child+1]) {
                child++;
            }
            if(array[child] > array[parent]) {
                swap(array,child,parent);
                parent = child;
                child = 2*parent+1;
            }else {
                break;
            }
        }
    }

    /**
     * 6.快排法
     *时间复杂度：N*logN
     *      最好情况 ：N*logN
     *      最坏情况：N^2  有序（只有单树的情况，树的高度为n）、逆序的时候，时间复杂度会高  优化！！！
     *空间复杂度：
     *      最好情况：logN
     *      最坏情况：N
     * 稳定性：不稳定
     * @param array
     */
    public static void quickSort1(int[] array) {

        quick(array,0,array.length - 1);  //给下标
    }
    public static void quick(int[] array,int start,int end) {
        if(start >= end) {  //注意此处是大于等于 而不是=号，大于的时候代表左边为空了没有值，即是start=0,end = -1
            return;
        }

        //进行优化，三数取中法
        int index = midThree(array,start,end);
        swap(array,index,start);

        int pivot = partition(array,start,end);  //进行划分
        quick(array,start,pivot - 1);  //左边进行排序
        quick(array,pivot + 1,end);   //右边进行排序
    }

    private static int midThree(int[] array,int left,int right) {
        int mid = (left+right) / 2;
        //6  8
        if(array[left] < array[right]) {
            if(array[mid] < array[left]) {
                return left;
            }else if(array[mid] > array[right]) {
                return right;
            }else {
                return mid;
            }
        }else {
            //array[left] > array[right]
            if(array[mid] < array[right]) {
                return right;
            }else if(array[mid] > array[left]) {
                return left;
            }else {
                return mid;
            }
        }

    }
    //划分的方法 挖坑法
    public static int partition(int[] array,int left,int right) {
        int tmp = array[left];
        while(left < right) {
            //左边做基准，要先走右边，不然最后相遇的地方会出错，会相遇到比基准大的地方

            //因为基准在左边，所以先从右边进行找小的值，把小的值转移到左边
            while( left < right && array[right] >= tmp) {   //注意此处必须取等，不然会陷入循环 如：6 2 1 6
                right--;
            }
            //走到这说明right下标的值就是右边第一个小于tmp的数，给到最左边
            array[left] = array[right];
            while( left < right && array[left] <= tmp) {   //注意此处必须取等，不然会陷入循环 如：6 2 1 6
                left++;
            }
            //走到这说明left下标的值就是左边第一个大于tmp的数，给到最右边
            array[right] = array[left];
        }
        //循环走完说明相遇了，把tmp的值给到left或者right
        array[left] = tmp;
        return left;  //返回下标
    }
    public static int partition2(int[] array,int left,int right) {
        int tmp = array[left];
        int ret = left;
        while(left < right) {
            while(left < right && array[right] >= tmp) {
                right--;
            }
            while(left < right && array[left] <= tmp) {
                left++ ;
            }
            swap(array,left,right);
        }
        //说明相遇
        swap(array,ret,left);
        return left;
    }
    //hoare法  (这个感觉容易理解点)
    public static int partition3(int[] array,int left,int right) {
        int tmp = array[left];
        int ret = left;
        while (left < right) {
            //左边做基准，要先走右边，不然最后相遇的地方会出错，会相遇到比基准大的地方
            //此时在进行交换，就会发生错误，导致比基准大的跑到最前面了，应该是小于基准的跑到前面去


            //右边right找到比基准小的停下来
            while(left < right && array[right] >= tmp) {
                right--;
            }
            //左边left找到比基准大的停下来
            while(left < right && array[left] <= tmp) {
                left++;
            }
            swap(array,left,right);
        }
        //走到这说明相遇了，left的值和tmp进行交换
        swap(array,ret,left);
        return left;
    }


    /**
     * 7.归并排序
     * 时间复杂度：N*logN
     * 空间复杂度：N
     * 稳定性：稳定的排序
     *       插入排序    冒泡排序  归并排序
     * @param array
     */
    //递归实现的归并排序
    public static void mergeSort1(int[] array) {
        mergeSortFunc(array,0,array.length-1);
    }
    //分解的代码
    private static void mergeSortFunc(int[] array,int left,int right) {
        if(left >= right) {
            return;
        }

        int mid = (left+right) / 2;
        mergeSortFunc(array,left,mid);
        mergeSortFunc(array,mid+1,right);
        merge(array,left,right,mid);
    }
    //主要实现的代码
    //合并的代码
    private static void merge(int[] array,int start,int end,int mid) {
        int s1 = start;
        int e1 = mid;
        int s2 = mid + 1;
        int e2 = end;
        int[] tmp = new int[end - s1 + 1];
        int k = 0;  //记录新数组的下标
        while(s1 <= mid && s2 <= end) {
            if(array[s1] > array[s2]) {  //s2小，把小的放进新数组里
                tmp[k++] = array[s2++];
               // k++;
               // s2++;
            } else {
                tmp[k++] = array[s1++];
            }
        }
        while(s1 <= mid) {   //说明s1所在数组内还有数据
            tmp[k++] = array[s1++];
        }
        while(s2 <= end) {   //说明s2所在数组内还有数据
            tmp[k++] = array[s2++];  //把s2所在数组的数据添加到新数组内
        }

        //再拷贝到原来数组中去
        for (k = 0; k < tmp.length; k++) {
            array[k + start] = tmp[k];
        }
    }



    /**
     * 计数排序
     * 时间复杂度： O(N+范围)
     * 空间复杂度：O(范围)
     * 稳定性：
     * @param array
     */
    public static void countSort(int[] array) {
        //1.找到数组中的最大和最小值，用来确定新数组的大小
        int max = array[0];
        int min = array[0];
        for (int i = 1; i < array.length; i++) {
            if(array[i] < min) {
                min = array[i];
            }
            if(array[i] > max) {
                max = array[i];
            }
        }
        //2.建立新数组
        int[] len = new int[max - min + 1];  //就是计数数组

        //3.遍历老数组，记录每个数字出现的次数
        for (int i = 0; i < array.length; i++) {
            len[array[i] - min]++;    //计数数组中放的就是出现的次数
        }

        //4.遍历计数数组，把数字再重新放到老数组中去
        int index = 0; //记录老数组array的下标
        for (int i = 0; i < len.length; i++) {
            while(len[i] > 0) {
                //这里要加上最小值，反映出原先的值
                array[index] = i + min;
                len[i]--;
                index++;
            }
        }
    }


}
